#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<int> traverse(TreeNode *root)
    {
        vector<int> res;
        if (root == nullptr)
        {
            return res;
        }
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode *cur = que.front();
                que.pop();
                res.push_back(cur->val);
                if (cur->left)
                {
                    que.push(cur->left);
                }
                if (cur->right)
                {
                    que.push(cur->right);
                }
            }
        }
        return res;
    }

    // TreeNode *recursion(vector<int> &inorder, vector<int> postorder)
    // {
    //     if (postorder.size() == 0)
    //     {
    //         return nullptr;
    //     }
    //     TreeNode *root = new TreeNode(postorder[postorder.size() - 1]);
    //     if (postorder.size() == 1)
    //     {
    //         return root;
    //     }
    //     int index = 0;
    //     int length = inorder.size();
    //     for (int i = 0; i < length; i++)
    //     {
    //         if (inorder[i] == postorder[postorder.size() - 1])
    //         {
    //             index = i;
    //             break;
    //         }
    //     }
    //     vector<int> left_inorder(inorder.begin(), inorder.begin() + index);
    //     vector<int> right_inorder(inorder.begin() + index + 1, inorder.end());

    //     postorder.resize(postorder.size() - 1);
    //     vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
    //     vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end());

    //     root->left = recursion(left_inorder, left_postorder);
    //     root->right = recursion(right_inorder, right_postorder);

    //     return root;
    // }
    // TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    // {
    //     if (inorder.size() == 0 || postorder.size() == 0)
    //     {
    //         return nullptr;
    //     }
    //     return recursion(inorder, postorder);
    // }

    TreeNode *recursion(vector<int> &inorder, int inorder_start, int inorder_end, vector<int> &postorder, int postorder_start, int postorder_end)
    {
        if (postorder_end - postorder_start == 0)
        {
            return nullptr;
        }
        TreeNode *root = new TreeNode(postorder[postorder_end - 1]);
        if (postorder_end - postorder_start == 1)
        {
            return root;
        }
        int index = 0;
        for (int i = 0; i < inorder_end; i++)
        {
            if (inorder[i] == postorder[postorder_end - 1])
            {
                index = i;
                break;
            }
        }
        int left_inorder_start = inorder_start;
        int left_inorder_end =  index;
        int right_inorder_start = index + 1;
        int right_inorder_end = inorder_end;

        int left_postorder_start = postorder_start;
        int left_postorder_end = postorder_start + index - inorder_start;
        int right_postorder_start = postorder_start + index - inorder_start;
        int right_postorder_end = postorder_end - 1;


        root->left = recursion(inorder, left_inorder_start, left_inorder_end, postorder, left_postorder_start, left_postorder_end);
        root->right = recursion(inorder, right_inorder_start, right_inorder_end, postorder, right_postorder_start, right_postorder_end);

        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (inorder.size() == 0 || postorder.size() == 0)
        {
            return nullptr;
        }
        return recursion(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

int main()
{
    vector<int> inorder{1, 2, 3, 4};
    vector<int> postorder{4, 3, 2, 1};
    Solution sol;
    TreeNode *root = sol.buildTree(inorder, postorder);
    vector<int> res = sol.traverse(root);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}